package yifeng.program;

import java.util.ArrayList;
import java.util.List;

public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
	}
	
	
	public static void quickSort(int[] a){
		
	}
	
	public static int partition(int[] a, int startIndex, int endIndex){
		//to do:越界判断
		
		int valve = a[startIndex];
		
		List<Integer> smaller = new ArrayList<Integer>();
		List<Integer> bigger = new ArrayList<Integer>();
		
		for(int i = startIndex + 1; i <= endIndex; i++){
			if(a[i] <= a[startIndex])
				smaller.add(a[i]);
			else
				bigger.add(a[i]);
		}
		
		int index = startIndex;
		for(int i = 0; i < smaller.size(); i++)
			a[index++] = smaller.get(i);
		
		a[index++] = valve;
			
		for(int i = 0; i < bigger.size(); i++)
			a[index++] = bigger.get(i);
		
		
		return startIndex + smaller.size();
	}
}
